home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C/C++ Users Group Library 1996 July
/
C-C++ Users Group Library July 1996.iso
/
listings
/
v_09_02
/
9n02039a
< prev
next >
Wrap
Text File
|
1990-11-10
|
6KB
|
228 lines
Listing 4.
/* sltest.c */
#define SLTEST 1
#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>
#include "skiplist.h"
/* globals */
int listsize; /* size of our test list */
int maxlevel = MAXLEVEL;
int partition;
int *emptr; /* dynamic array of list elements */
int nnodes; /* count of nodes allocated */
long ctotals; /* total number of comparisons */
int comps; /* temporary counter */
int mincomps;
int maxcomps;
#define COMPMAX 80 /* width of screen */
int compary[COMPMAX] = { 0 }; /* for graph routine */
int overflow = 0;
int levels[MAXLEVEL] = { 0 };
jmp_buf errbuf; /* short circuit when out of memory */
NODE *testlist;
int orderflag; /* non-zero for random insertions */
#define SL_RAND_MAX 32767
int intcmp(a, b) /* test comparison routine */
KEYTYPE a, b;
{
comps += 1; /* track length of search path */
if(a < b)
return(-1);
else if(a == b)
return(0);
else
return(1);
}
main(argc, argv)
int argc;
char *argv[];
{
if(argc < 6)
usage();
if((listsize = atoi(argv[i])) < 1)
usage();
if(listsize > SL_RAND_MAX)
{
listsize = SL_RAND_MAX;
printf("listsize reduced to %d\n", SL_RAND_MAX);
}
if((maxlevel = atoi(argv[2])) < 1)
usage();
if(maxlevel > MAXLEVEL)
{
maxlevel = MAXLEVEL;
printf("maxlevel reduced to %d\n", MAXLEVEL);
}
if((partition = atoi(argv[3])) < 1)
|| (partition >= maxlevel))
{
usage();
}
slsrand((unsigned) atoi(argv[4]));
orderflag = atoi(argv[5]);
list_init();
list_build();
list_test();
list_stats();
exit(EXIT_SUCCESS);
}
usage() /* describe command line errors */
{
printf("\nUsage:\t");
printf("sltest <size> <maxlevel> <partition> <seed> <flag>\n");
printf("\t<size> of test list (>= 1)\n");
printf("\t<maxlevel> max number of pointers per node (>= 1)\n");
printf("\t<partition> (>= 1 && < maxlevel [= %d])\n", maxlevel);
printf("\t<seed> for the random number generator\n");
printf("\t<flag> 0 for in-order insertions, otherwise random");
exit(EXIT_FAILURE);
}
list_init()
{
if((emptr = (int *) calloc(listsize, sizeof(int)))
== NULL)
{
nomem();
}
if((testlist = newlist()) == NIL)
nomem();
}
nomem()
{
printf("Not enough memory for a list of size %u\n",
(unsigned)listsize);
exit(EXIT_FAILURE);
}
list_build()
{
unsigned slrand();
unsigned i;
if(setjmp(errbuf))
listsize = nnodes; /* largest possible */
else if(orderflag == 0)
{
for(nnodes = 0, i = 1; i <= listsize; )
insert(testlist, i++);
}
else
{
for(nnodes = 0; nnodes < listsize; )
insert(testlist, slrand());
}
}
list_test()
{
int i;
ctotals = 0L;
mincomps = listsize;
maxcomps = 0;
for(i = 0, comps = 0; i < listsize; ++i, comps = 0)
{
search(testlist, emptr[i]);
ctotals += (long) comps;
if(comps < mincomps)
mincomps = comps;
else if(comps > maxcomps)
maxcomps = comps;
if(comps < COMPMAX)
compary[comps] += 1;
else
overflow += 1; /* won't fit on screen */
}
}
/* for computing behavior of balanced trees */
unsigned treelevels[] = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16 };
unsigned powersof2[] = {
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,
4096, 8192, 16384, (SL_RAND_MAX + 1) };
int depth;
long accumulator;
list_stats() /* print out statistics */
{
int i;
int scale;
int temp;
int cmax;
printf("\nskiplist size = %d", listsize);
printf("\npointers per level = ");
for(i = 0; i < maxlevel; i += 1)
printf("%d ", levels[i]);
printf("\ncomparisons per search: ");
printf("mean = %.3f, minimum = %d, maximum = %d\n",
((float)ctotals) / ((float)listsize),
mincomps, maxcomps);
if(overflow != 0) /* graph won't fit on screen */
printf("distribution of comparisons overflows buffer\n");
else
{
cmax = 0;
for(i = mincomps; i <= maxcomps; i += 1)
{
if(compary[i] > cmax)
cmax = compary[i];
}
scale = cmax / 10;
if(scale == 0) /* watch out for cmax < 10!! */
scale = 1;
temp = cmax % 10;
if((temp / scale) > 5)
scale += 1;
for(temp = cmax; temp >= 0; temp -= scale)
{
if(temp <= scale) /* last pass through */
if(scale > 1) /* make sure we */
temp = 1; /* print all */
for(i = mincomps; i <= maxcomps; i += 1)
{
if(compary[i] / temp)
printf("*");
else
printf(" ");
}
printf("\n");
}
printf("distribution from minimum through maximum:");
printf(" scale = %d:1\n", scale);
}
for(i = 0; (powersof2[i] - 1) < listsize; i += 1)
;
depth = i--; /* maximum for perfectly balanced tree */
accumulator = ((long) treelevels[i])
* ((listsize - powersof2[i--]) + 1);
while(i >= 0)
{
accumulator += (long) (treelevels[i]
* powersof2[i--]);
}
printf("for perfect trees: ");
printf("mean = %.3f, minimum = 1, maximum = %d\n",
(((float)accumulator) / ((float)listsize)), depth);
printf("for degenerate trees: ");
printf("mean = %.3f, minimum = 1, maximum = %d\n",
((float) (listsize + 1) / 2), listsize);
}
/* EOF */